/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2022/9/6
 * \* Time: 7:21
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class test {
    public static void main(String[] args) {
        int[] nums = new int[] { 1, 3, 7, 8, 2, 9, 6, 0, 5, 4 };
        sort5(nums,0,nums.length-1);
        for (int num : nums)
            System.out.print(num + " ");
    }

    //归并排序
    public static void sort5(int[]nums,int start,int end){
        if(start < end){
            int mid = (start + end) /2;
            sort5(nums,start,mid);
            sort5(nums,mid + 1,end);
            merge(nums,start,end);
        }
    }
    public static void merge(int[]nums,int left,int right){
        int[]temp = new int[nums.length];
        int mid = left + (right - left)/2;
        int p1 = left;
        int p2 = mid + 1;
        int k = left;
        while (p1 < mid && p2 <= right){
            if(nums[p1] <= nums[p2]){
                temp[k++] = nums[p1++];
            }else{
                temp[k++] = nums[p2++];
            }
        }
        while (p1 <= mid){
            temp[k++] = nums[p1++];
        }
        while (p2 <= right){
            temp[k++] = nums[p2++];
        }
        for(int i = left; i <= right;i++){
            nums[i] = temp[i];
        }
    }

    //快速排序
    public static void sort4(int[]nums,int start,int end){
        //终止条件
        if(start > end){
            return;
        }
        int left = start;
        int right = end;
        int temp = nums[left];
        while (left < right){
            while (left < right && nums[right] >= temp){
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= temp){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = temp;
        sort4(nums,start,left - 1);
        sort4(nums,left+1,end);
    }

    //选择排序
    public static void sort2(int[]nums){
        int n = nums.length;
        for(int i = 0; i < n-1;i++){
            int min = i;
            for(int j = i+1; j < n;j++){
                if(nums[j] < nums[min]){
                    min = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[min];
            nums[min] = temp;
        }
    }

    //插入排序
    public static void sort1(int[] nums){
        int n = nums.length;
        int pos,cur;
        for(int i = 1; i < n; i++){
            pos = i - 1;
            cur = nums[i];

            while (pos >= 0 && cur < nums[pos]){
                nums[pos+1] = nums[pos];
                pos--;
            }
            nums[pos+1] = cur;
        }
    }


    //冒泡排序
    public static void sort(int[]nums){
        int n = nums.length;
        for(int i = 0; i < n;i++){
            for(int j = 0; j < n - i - 1; j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j+1] = temp;
                }
            }
        }
    }
}
